/**
 * 
 */
package calculation.passed;

/**
 * @author xyyi
 *
 */
public class CountNumberOfKDigit {

	/**
	 * 
	 */
	int countNumberWithK(final int n, final int k) {
		assert (n >= 0 && k > 0 && k <= 9);

		int digit = 0, number = n, counter = 1;
		int index = 0; // index of digit in number
		while (number != 0) {
			digit = number % 10;
			number = number / 10;
			if (digit == k) {
				counter = 0;
				counter += digit * Math.pow(9, index++);
			} else if (digit < k) {
				counter += digit * Math.pow(9, index++);
			} else { // currDigit > k
				counter += (digit - 1) * Math.pow(9, index++);
			}
		}

		return n + 1 - counter;
	}

	int countWithK(final int n, final int k) {
		int currDigit = 0, number = n, counter = 0;
		int divisor = 1;
		int size = 0; // size is length - 1 of n 
		while (number / divisor >= 10) {
			divisor *= 10;
			size++;
		}

		while (divisor != 0) {
			currDigit = number / divisor;
			number %= divisor;
			divisor /= 10;
			if (currDigit == k) {
				counter += currDigit * Math.pow(9, size--);
				break;
			} else if (currDigit < k) {
				counter += currDigit * Math.pow(9, size--);
			} else { // currDigit > k
				counter += (currDigit - 1) * Math.pow(9, size--);
			}
			if (size < 0)
				counter++;
		}

		return n + 1 - counter;
	}

	/**
	 * http://www.cnblogs.com/baother/archive/2012/11/26/2789832.html
	 * k is the digit from 0 to 9.
	 * find how many k digit from 0 to n
	 * 
	 * assume the number is abcd
	 * the digit k on b is based on 
	 * case1: if b < k, counter = a*100
	 * case2: if b == k, counter = a*100 + cd + 1
	 * case3: if b > k, counter = (a+1) *100
	 */
	int countNumberOfK(int n, int k) {
		assert (k >= 0 || k <= 9);

		n = n < 0 ? -n : n;
		int factor = 1, currDigit = 0, highNumber = 0, lowNumber = 0, counter = 0;
		while (n / factor != 0) {
			lowNumber = n % factor;
			currDigit = n / factor % 10;
			highNumber = n / (factor * 10);

			if (currDigit < k) {
				counter += highNumber * factor;
			} else if (currDigit == k) {
				counter += highNumber * factor + lowNumber + 1;
			} else { // currNumber > k
				counter += (highNumber + 1) * factor;
			}
			factor *= 10;
		}

		return counter;
	}

	/**
	 * 
	 */
	public CountNumberOfKDigit() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		CountNumberOfKDigit cnok = new CountNumberOfKDigit();
		int[] n = { 0, 1, 4, 5, 6, 14, 15, 16, 49, 50, 51, 54, 55, 56, 104,
				105, 106, 149, 150, 151, 154, 155, 156, 499, 500, 501, 554,
				555, 556, Integer.MAX_VALUE - 1, Integer.MAX_VALUE };
		int k = 5;
		for (int i = 0; i < n.length; i++) {
			//System.out.println(cnok.countNumberOfK(n[i], k));
			//System.out.println(cnok.countNumberWithK(n[i], k));
			System.out
					.printf("The number of integers containing %d in [0, %d]: {output: %d}, {expected: %d}  \n",
							k, n[i], cnok.countWithK(n[i], k),
							cnok.countNumberWithK(n[i], k));
		}

	}
}
